package graph;

import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import util.AbstractColouring;
import util.ColourDegree;

/**
 *
 * @author Admin
 */
public class Shrub<V, E extends Graph.Edge<V>> extends AbstractColouring<V, E> {

    private Tree<V, E> tree;
//    private V root = null;
    private V rootPlus;
    private Map<V, Set<V>> nodes;
    private List<V> indexNodes;

    public Shrub(Tree<V, E> tree, V rootPlus, Map<V, Set<V>> nodes, List<V> indexNodes) {
        super(tree);
        this.rootPlus = rootPlus;
        this.nodes = nodes;
        this.indexNodes = indexNodes;
        this.tree = tree;
    }

    /**
     * @return the root
     */
    public V root() {
        return tree.root();
    }

    public V getV(int index) {
        return indexNodes.get(index);
    }

    public List<V> indexNodes() {
        return indexNodes;
    }

    /**
     * @return the root plus
     */
    public V rootPlus() {
        return rootPlus;
    }

    public Set<V> vi() {
        return nodes.keySet();
    }

    public Set<V> children(V vi) {
        return nodes.get(vi);
    }

    public Map<V, Set<V>> nodes() {
        return nodes;
    }

    public void colour() {
        marked.clear();
        int index = 0;
        int numChildren = nodes.size();
        int max = (int) Math.pow(2, nodes.size());
        do {
            invertVi(index, numChildren);
            index++;
        } while (index <= max && !is2aliecShrub());
    }

    public Set<Integer> computeSetD0() {
        Set<Integer> setD0 = new HashSet<Integer>();
        int numChildren = nodes.size();
        if (numChildren > 0) {
            int max = (int) Math.pow(2, nodes.size());
            int index = 0;
            do {
                marked.clear();
                invertVi(index, numChildren);
                index++;
                if (is2aliecShrub()) {
                    setD0.add(getColourDegree(rootPlus).aColour);
                }
            } while (index < max);
        } else {
            setD0.add(1);
        }
        return setD0;
    }

    private void invertVi(int position, int numChildren) {
        String bin = padLeft(Integer.toBinaryString(position), numChildren);
        for (int i = 0; i < bin.length(); i++) {
            marked.put(getV(i), bin.charAt(i) == '1');
        }
    }

    private String padLeft(String s, int n) {
        int width = n - s.length();
        if (width <= 0) {
            return s;
        }
        return String.format("%0" + width + "d%s", 0, s);
    }

    private boolean is2aliecShrub() {
        // change (add root)
        ColourDegree dr = getColourDegree(rootPlus());
        for (V v : indexNodes()) {
            ColourDegree dv = getColourDegree(v);
            // same a-degree or b-degree
            if (dv.aColour == 0 && dr.bColour == dv.bColour) {
                return false;
            } else if (dv.bColour == 0 && dr.aColour == dv.aColour) {
                return false;
            } else if ((dv.aColour == dr.aColour) && (dv.bColour == dr.bColour)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public String toString() {
        return rootPlus + " -> " + nodes;
    }

}
